干物妹！小埋！第二弹 比赛题解

发表于 | 更新于 | 阅读次数：
本文字数： 4.4k | 阅读时长 ≈ 4 分钟

Problem A（小埋与Chicken rabbit with cages）：

此题为典型的鸡兔同笼问题，原意用于照顾蒟蒻，故比较简单，模拟解方程组即可。

$ x+y=head $

$ 2x+4y=leg $

附标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
namespace UMR/*防抄袭命名空间*/
{
    long long a=0,b=0,x=0,y=0;
	int n;
};
using namespace std;
using namespace UMR;
int main()
{
	cin>>n;
	for(int d=1;d<=n;d++)
	{
		cin>>a>>b;
		y=(b-2*a)/2;
		x=a-y;
		cout<<x<<" "<<y<<endl;
	}
}

Problem B（小埋与哥哥的企划）：

采用深度优先搜索（DFS）算法，可以从两个角度出发：

（1） 以专家为出发点，每个专家要么选择他要么不选择他，当所有专家都确定是否选择后，这代表一种备选的方案，但是这个方案是否可行，需要检查是否所有n个问题都得到解决，在搜索的过程中记录最少的专家数。

（2） 以问题为出发点，每个问题都可能会有若干个专家可以解决该问题，依次尝试选择每个专家，然后继续下个问题，直到所有问题被解决。

我们考虑以第（2）个角度出发，尝试如何优化和剪枝，基本思想是：对于某个问题，如果只有一个专家能解决，则该专家是必选的，这是其中一个优化策略。对于尝试对某个问题选择专家时，如果当前已选择的专家数>=已记录的最少专家数-1，则表示即使选择该专家，其最终方案的专家数也不可能少于当前记录的最少专家数，因此不需要尝试选择该专家。

进一步的优化还可以这样做：在调用搜索函数前，检查每一位专家能解决的问题，如果该专家能解决的问题，另一位专家都能解决，则该专家不需要参与选择，即可以在数组中标志该专家为已选择（注意，虽然将他标志为已选择，但是该专家不计算在已选择专家数中），这样在递归搜索时其搜索的规模将会降低。

附标程（效率还是比较低）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstring>
namespace UMR/*防作弊专用命名空间*/
{
    int a[61][7],wo[61],used[61],n,w,dec[61],ans,min;
};
using namespace UMR;
using namespace std;
void dfs(int step)
{
    bool f=true;
    if (step>n)
    {
    	if (min>ans)
        min=ans;
    }
    else
    if (wo[step])
    dfs(step+1);
    else
    if (ans<min)
    for (int i=1; i<=w; i++)
    if (used[i]==0)
    {
    	f=true;
        for (int j=1; j<=a[i][0]; j++)
        if (a[i][j]==step)
        {
        	f=false;
            break;
        }
        if (not f)
        {
        	used[i]++;
            ans++;
            for (int j=1; j<=a[i][0]; j++)
            wo[a[i][j]]++;
            dfs(step+1);
            used[i]--;
            ans--;
            for (int j=1; j<=a[i][0]; j++)
            wo[a[i][j]]--;  	
         }
	}
}
int main ()
{
    scanf("%d%d",&n,&w);
    memset(a,0,sizeof(a));
    memset(wo,0,sizeof(wo));
    memset(used,0,sizeof(used));
    memset(dec,0,sizeof(dec));
    for (int i=1; i<=w; i++)
    {
    	scanf("%d",&a[i][0]);
      	for (int j=1; j<=a[i][0]; j++)
      	{
        	scanf("%d",&a[i][j]);
      	    if (dec[a[i][j]]!=-1)
            if (dec[a[i][j]]==0)
            dec[a[i][j]]=i;
            else
            dec[a[i][j]]=-1;
      	}      	
    }
    ans=0; 
    for (int i=1; i<=n; i++)
    if (dec[i]!=0 && dec[i]!=-1)
    { 
    	if (used[dec[i]]==0)  
        {
            ans++;
        	used[dec[i]]++;
        	for (int j=1; j<=a[dec[i]][0]; j++)
        	wo[a[dec[i]][j]]++;
        } 
    }
    min=2147483647;
    dfs(1);
    printf("%d",min);
    return 0;
}

Problem C（小埋与TSF的密信）：

跟普通的加密解密字符一样，只不过这道题要多做一步：

统计！

根据大量的英文文章字母统计，绝大部分的文章中字母”e”,”E”出现得最多，因此可以在此入手。

先将输入的加密后的字符进行统计，找出出现得最多的字母，根据这个字母与”e”,”E”的关系，即可按照正常的思路进行解密。

附标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
	char in,str[100000];
	long long a=1,max=0,ji=0;
	int zm[256]={0};
	while((in=getchar())!=EOF)
	{
		a++;
		str[a]=in;
		if(in<='Z'&&in>='A')
		{
			zm[in-65]++;
		}
		if(in>='a'&&in<='z')
		{
			zm[in-97]++;
		}
	}
	for(int t=0;t<=26;t++)
	{
		if(zm[t]>zm[max])
		{
			max=t;
		}
	}
	ji=max+65-'E';
	for(int t=2;t<=a;t++)
	{
		if(str[t]>='A'&&str[t]<='Z')
		{
			if(str[t]-ji<'A')
			{
				cout<<(char)(str[t]+26-ji);
			}
			else
			{
				if(str[t]-ji>'Z')
				{
					cout<<(char)(str[t]-26-ji);
				}
				else
				{
					cout<<(char)(str[t]-ji);
				}				
			}		    
			continue;
		}
		if(str[t]>='a'&&str[t]<='z')
		{
			if(str[t]-ji<'a')
			{
				cout<<(char)(str[t]+26-ji);
			}
			else
			{
				if(str[t]-ji>'z')
				{
					cout<<(char)(str[t]-26-ji);
				}
				else
				{
					cout<<(char)(str[t]-ji);
				}	
			}
			continue;
		}
		cout<<str[t];
	}		
}

比赛详见:https://www.luogu.org/contestnew/show/7846